package dynamicProgramming

// 动态规划--状态转移表寻找最短路径
func MinDistDP(matrix [][]int, n int) int {
	states := make([][]int, n)
	for i := 0; i < n; i++ {
		states[i] = make([]int, n)
	}
	// 初始化states第一行
	sum := 0
	for i := 0; i < n; i++ {
		sum += matrix[i][0]
		states[i][0] = sum
	}
	// 初始化states第一列
	sum = 0
	for j := 0; j < n; j++ {
		sum += matrix[0][j]
		states[0][j] = sum
	}
	for i := 1; i < n; i++ {
		for j := 1; j < n; j++ {
			// 每个节点只能往右或者往下移动，也就是说到达(i,j)的最短路径要么经过(i,j-1)，要么经过(i-1,j)
			// 也就是说min_dist(i,j)可以通过min_dist(i,j-1)和min_dist(i-1,j)两个状态推导出来
			// 状态转移方程 min_dist(i,j) = w[i][j] + min(min_dist(i,j-1), min_dist(i-1,j))
			states[i][j] = matrix[i][j] + Min(states[i][j-1], states[i-1][j])
		}
	}
	return states[n-1][n-1]
}

func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
